{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Measurement-based Quantum Approximate Optimization Algorithm\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polynomial Unconstrained Boolean Optimization Problem\n",
    "\n",
    "In the field of applied mathematics and theoretical computer science, **combinatorial optimization problem** is a class of problems aiming to find the optimal solution in a discrete solution space. In the tutorial [Quantum Approximate Optimization Algorithm](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html), we have already introduced general combinatorial optimization problems. Here we will focus on a specific type of combinatorial optimization problem: **polynomial unconstrained boolean optimization problem (PUBO)**.\n",
    "\n",
    "To be specific, a polynomial with $n$ variables of $x = \\{x_1,\\cdots,x_n\\}$ has the form of:\n",
    "\n",
    "$$\n",
    "C(x) = \\sum_{\\lambda \\in \\Lambda } \\alpha_{\\lambda} \\prod_{j \\in \\lambda} x_j,\\tag{1}\n",
    "$$\n",
    "\n",
    "where $x_i \\in \\{0,1\\}$ is a variable, $\\underset{j \\in \\lambda}{\\prod} x_j$ is a monomial, $\\lambda \\subseteq [n]:= \\{1, 2, ..., n\\}$ is a set of indexes, $\\Lambda$ is the set of index sets, $\\alpha_\\lambda$ is the real coefficient of monomial. In PUBO, $C(x)$ is called the objective polynomial. We hope to find an optimal solution $x^* = \\{x_1^*, x_2^*, ..., x_n^*\\} $ to maximize the value of $C(x)$, that is,\n",
    "\n",
    "$$\n",
    "x^* = \\underset{x}{\\text{argmax}} \\ C(x).\\tag{2}\n",
    "$$\n",
    "\n",
    "Polynomial unconstrained boolean optimization is a widely used optimization model. If the degree of the objective polynomial is two, it is called a quadratic polynomial combinatorial optimization problem, usually used to describe problems in graph theory, such as maximum independent set (MIS), maximum cut (Max-Cut), maximum set coverage (Max-Coverage), etc. It is also widely applicable in statistic physics, network design, Very Large Scale Integration Circuit (VLSI) design, cluster analysis, financial analysis, and machine scheduling. If the degree of the objective polynomial is larger than two, such a polynomial optimization will play an important role in signal processing (SP) and image reconstruction in computer vision (CV). However, it is NP-hard to find optimal solutions for PUBO in general."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Quantum Approximate Optimization Algorithm \n",
    "\n",
    "In 2014, Farhi et al. proposed the **quantum approximate optimization algorithm (QAOA)**, an iterative algorithm involving both classical and quantum computation [1]. This algorithm is designed to solve combinatorial optimization problems with the capability of a quantum computer, and also to demonstrate quantum advantages. For more details, please refer to the tutorial [Quantum Approximate Optimization Algorithm](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html). Here, we only briefly review the basic ideas and the implementation process of QAOA.\n",
    "\n",
    "To transform a classical combinatorial optimization problem into a quantum one, we need to encode variables to a quantum state and the objective polynomial to a Hamiltonian of a quantum system. We will explain these two steps as follows.\n",
    "\n",
    "### Encoding variables to a quantum state\n",
    "\n",
    "For variable $x$, each of its elements takes a value of either $0$ or $1$, which naturally corresponds to the quantum state $|0\\rangle$ and $|1\\rangle$. Thus, a string of boolean variables of length $n$ can be mapped to a quantum state with $n$ qubits, that is,\n",
    "\n",
    "$$\n",
    "|x\\rangle = |x_1x_2...x_n\\rangle.\\tag{3}\n",
    "$$\n",
    "\n",
    "Thereby, to find an optimal solution $x^{*}$ is to find a quantum state $|x^{*} \\rangle$.\n",
    "\n",
    "### Encoding the objective polynomial to a Hamiltonian \n",
    "\n",
    "For the objective polynomial $C(x)$, we can encode it to the diagonal of a Hamiltonian $H_C$, where for any $x$, it satisfies that\n",
    "\n",
    "$$\n",
    "H_C |x\\rangle = C(x) |x\\rangle.\\tag{4}\n",
    "$$\n",
    "\n",
    "It is worth noting that, if $x^{*}$ is one of the optimal solutions to the original problem, then it satisfies\n",
    "\n",
    "$$\n",
    "\\langle x^{*} | H_{C} |x^{*} \\rangle = C(x^{*}).\\tag{5}\n",
    "$$\n",
    "\n",
    "Therefore, to find an optimal solution $x^{*}$ of the original optimization problem is equivalent to find an eigenstate $|x^{*} \\rangle$ corresponding to a maximal eigenvalue of $H_C$. That is to solve\n",
    "\n",
    "$$\n",
    "|x^{*}\\rangle = \\underset{|x\\rangle}{\\text{argmax}} \\ \\langle x | H_C | x \\rangle.\\tag{6}\n",
    "$$\n",
    "\n",
    "**Note**: The above definition gives a way to encode an objective polynomial to Hamiltonian. But how can we quickly find the exact expression of $H_C$? Let us consider a simple example first. Assume $C(x) = 1-2x$, so $C(0) = 1$ and $C(1) = -1$. It is clear that we should take $H_C = Z$ as the corresponding Hamiltonian, where $Z$ denotes the Pauli Z gate. In a more general case, we can substitute the variable $x$ in the objective polynomial $C(x)$ to variable $z$ with the relation of $1-2x_i = z_i$ (or $x_i = (1-z_i)/2$) and then rewrite each scalar variable $z_i$ to Pauli operator $Z_i$, where $i$ stands for the underlying system. It is easy to check that the resulting Hamiltonian satisfies $H_C |x\\rangle = C(x) |x\\rangle$.\n",
    "\n",
    "For users' convenience, we provide a function `get_cost_hamiltonian` in `qaoa` to obtain the Hamiltonian of a given polynomial. We can directly import it by\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import get_cost_hamiltonian\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QAOA circuit\n",
    "\n",
    "After encoding the variables and objective function, we introduce an auxiliary Hamiltonian\n",
    "\n",
    "$$\n",
    "H_B = \\bigotimes_{j=1}^n X_j,\\tag{7}\n",
    "$$\n",
    "\n",
    "where $X_j$ is the Pauli $X$ gate applied to qubit $j$. Inspired by the quantum adiabatic theorem [2,3], we hope to evolve the eigenstate $|+\\rangle^{\\otimes n}$ of $H_B$ 's maximal eigenvalue, to the eigenstate of $H_C$ 's maximal eigenvalue. This can be achieved by the following,\n",
    "\n",
    "$$\n",
    "|\\gamma,\\beta\\rangle :=  \\left(\\prod_{i=1}^p U_B(\\beta_i)U_{C}(\\gamma_i)\\right)|+\\rangle^{\\otimes n},\\tag{8}\n",
    "$$\n",
    "\n",
    "where $U_{C}(\\gamma) = e^{-i\\gamma H_{C}}$, $U_B(\\beta) = e^{-i \\beta H_B}$ are unitaries, $\\beta$, and $\\gamma$ are the training parameters, and $p$ is the algorithm's depth. The larger the depth $p$ is, the more accurate the final solution would be, but in the expense of more computational resources.\n",
    "\n",
    "Please refer to the tutorial [Quantum Approximate Optimization Algorithm](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html) for more details of QAOA in the circuit model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Measurement-based QAOA\n",
    "\n",
    "[Measurement-based quantum computation (MBQC)](MBQC_EN.ipynb) provides a completely different computation model from the conventional circuit model. Due to the universality of MBQC, every quantum circuit model can be translated to its MBQC equivalent. In a recent work [4], a measurement-based variational quantum eigensolver (MB-VQE) is proposed. Following the same spirit, we propose a **measurement-based quantum approximate optimization algorithm (MB-QAOA)** here as an introductory tutorial of measurement-based quantum algorithms. Just like the circuit model, different MBQC algorithms may also be equivalent. Our proposed MB-QAOA is relatively concise and will be simulated by our MBQC module.\n",
    "\n",
    "\n",
    "### Techniques\n",
    "\n",
    "The key point of QAOA is to perform the iterative operations of $U_{C}$ and $U_B$ to an initial quantum state. We will first introduce two lemmas to show how these two operations can be easily realized in MBQC. Interested readers can either prove these results on your own or simply refer to [5].\n",
    "\n",
    "**Lemma 1:** Let $|\\psi\\rangle_{1 \\cdots k}$ be a quantum state with $k$ qubits labeled as ${1, ..., k}$. The evolution under $e^{i\\theta Z_1Z_2\\cdots Z_k}$ can be realized by the following:\n",
    "\n",
    "$$\n",
    "M_0^{YZ}(2\\theta) \\left(\\prod_{j=1}^{k} CZ_{0,j}\\right) \\Big(|+\\rangle_0 \\otimes |\\psi\\rangle_{1 \\cdots k}\\Big) \\longrightarrow \\left(\\prod_{j=1}^{k} Z_j\\right)^{s_0}\\, e^{i\\theta Z_1Z_2\\cdots Z_k}\\, |\\psi\\rangle_{1 \\cdots k}.\\tag{9}\n",
    "$$\n",
    "\n",
    "That is, initialize a plus state on qubit $0$; apply CZ gates between qubit $0$ and each qubit of input state $|\\psi\\rangle_{1 \\cdots k}$; perform a projective measurement on qubit $0$ in the $YZ$ plane with an angle $2\\theta$. After this measurement, the state of qubit $1,\\cdots,k$ will be transformed into the state on the right side of the arrow, that is $e^{i\\theta Z_1Z_2\\cdots Z_k}|\\psi\\rangle_{1 \\cdots k}$, with byproducts $\\left(\\prod_{j=1}^{k} Z_j\\right)^{s_0}$ applied to it, where $s_0 \\in \\{0,1\\}$ is the measurement outcome of qubit $0$.   \n",
    "\n",
    "Finally, the operation $U_C$ can be realized by successively performing $e^{i\\theta Z_1Z_2\\cdots Z_k}$ several times.\n",
    "\n",
    "**Lemma 2:** Let $|\\psi\\rangle_1$ be a single-qubit quantum state on qubit $1$. The evolution under $R_x(\\theta_2)R_z(\\theta_1)$ can be realized by the following:\n",
    "\n",
    "$$\n",
    "M_2^{XY}\\big((-1)^{1+s_1}\\theta_2\\big) M_1^{XY}(-\\theta_1) \\Big(CZ_{23} CZ_{12}\\Big) \\Big(|\\psi\\rangle_1 \\otimes |+\\rangle_2 \\otimes |+\\rangle_3 \\Big) \\longrightarrow Z^{s_1} X^{s_2} R_{x}(\\theta_2) R_z(\\theta_1) |\\psi\\rangle_3.\\tag{10}\n",
    "$$\n",
    "\n",
    "That is, initialize a plus state on qubit $2$ and qubit $3$ respectively; apply CZ gates to qubit $1$ and qubit $2$, qubit $2$ and qubit $3$; perform a projective measurement on qubit $1$ in the $XY$ plane with an angle of $-\\theta_1$ and record the measurement outcome as $s_1$; then perform a projective measurement on qubit $2$ in the $XY$ plane with an angle of $(-1)^{1+s_1}\\theta_2$ and record the measurement outcome as $s_2$. Finally, the state on qubit $3$ will be $R_{x}(\\theta_2) R_z(\\theta_1) |\\psi\\rangle_3$ with byproducts $Z^{s_1} X^{s_2}$ applied to it.   \n",
    "\n",
    "The operation $U_B$ can be realized by using Lemma 2 multiple times with $\\theta_1 = 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With these two lemmas, I am sure you already have a rough idea of how to implement MB-QAOA. Next, we will give a concrete explanation by the standard \"three-step\" process of MBQC: graph state preparation, single-qubit measurement, and byproduct correction.\n",
    "\n",
    "\n",
    "### Graph state preparation\n",
    "\n",
    "Due to the one-to-one correspondence between a graph and its graph state, it suffices to directly work with a graph in the following. We call it an **MB-QAOA graph**.\n",
    "\n",
    "#### One-layer MB-QAOA graph\n",
    "\n",
    "According to the number of variables $n$ of $C(x)$, we first arrange $n$ green vertices, $n$ blue vertices and $n$ gray vertices respectively in columns. Denote green vertices as $G^v$, blue vertices as $B^v$, and gray vertices as \n",
    "$H^v$, where $1 \\leq v \\leq n$. Then connect green and blue vertices, blue and gray vertices on the same rows. Substitute the variables of $C(x)$ by $x_i = (1-z_i)/2$ and obtain a new function $C(z)$ which has a form of\n",
    "\n",
    "$$\n",
    "C(z) = c + \\sum_{v} \\eta_v z_v + \\sum_{S} \\eta_S \\prod_{j \\in S} z_j,\\tag{11}\n",
    "$$\n",
    "\n",
    "where $c$ is the constant item, $1 \\leq v \\leq n$ is the index of linear item with coefficient $\\eta_v$, $S$ is the index set of non-linear item with coefficient $\\eta_S$. We complement the absent linear items with coefficient $0$. For each non-linear monomial  $\\prod_{j \\in S} z_j$ in $C(z)$, we add a new red vertex $R^S$ to the left of the green vertices, and connect $R^S$ to $G^v$ for all $v\\in S$.\n",
    "\n",
    "The resulting graph is called the \"one-layer MB-QAOA graph\". According to the Lemmas above, we will measure red vertices to realize the evolution of $U_C$, and measure green and blue vertices to realize the evolution of $U_B$. The gray vertices are left to store the post-measurement state. Figure 1 gives a specific example of a one-layer MB-QAOA graph. \n",
    "\n",
    "![QAOA graph](./figures/mbqc-fig-qaoa_graph_1.jpg)\n",
    "<div style=\"text-align:center\">Figure 1: An example of one-layer MB-QAOA graph, with an objective function of $C(z) = z_2 + z_1 z_3 + 5 z_3 z_4 - 2 z_1 z_2 z_4$ after variable substitution.</div>\n",
    "\n",
    "#### $p$-layer MB-QAOA graph\n",
    "\n",
    "As is mentioned above, a $p$-layer QAOA circuit consists of iterative action of two operations ($U_C$ and $U_B$) $p$ times. This holds for MB-QAOA as well. For general depth $p$, we need to repeat the one-layer QAOA graph $p$ times, with the green vertices in the next layer (corresponding to the input state) overlapping to the gray vertices in a previous layer (corresponding to the output state), to ensure that the quantum state can evolve consecutively. The gray vertices on the rightmost are left to store the post-measurement state. Figure 2 gives a specific example of the $p$-layer MB-QAOA graph.   \n",
    "\n",
    "![QAOA graph](./figures/mbqc-fig-qaoa_graph_p.jpg)\n",
    "<div style=\"text-align:center\">Figure 2: An example of $p$-layer MB-QAOA graph, with an objective function of $C(z) = z_2 + z_1 z_3 + 5 z_3 z_4 - 2 z_1 z_2 z_4$ after variable substitution.</div>\n",
    "\n",
    "In `qaoa`, we provide a function `preprocess` to generate the MB-QAOA graph. We can import this function directly with the following line.\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import preprocess\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Single-qubit measurement\n",
    "\n",
    "After preparing a graph state, the next step is to design a specific measurement for each qubit. According to the Lemmas above, we are capable of calculating all measurement angles with previous measurement outcomes considered.\n",
    "\n",
    "Let $p$ be a given depth of the MB-QAOA circuit. We implement measurements on vertices of the MB-QAOA graph, from left to right and top to bottom in order. For vertices on the $l$-th layer, their measurement information is given in Table 1:\n",
    "\n",
    "|Vertex|Measurement Plane|Measurement Angle|Measurement Outcome|\n",
    "|:---:|:---:|:---:|:---:|\n",
    "|$$R_l^S$$|$$M^{YZ}$$|$$T \\Big(1+\\sum_{v \\in S}\\sum_{k=1}^{l-1}s(B_k^v)\\Big) \\cdot 2 \\eta_S \\gamma_l $$|$$s(R_l^{S})$$|\n",
    "|$$G_l^v$$|$$M^{XY}$$|$$T \\Big(1+\\sum_{k=1}^{l-1}s(B_k^v)\\Big) \\cdot 2 \\eta_v \\gamma_l $$|$$s(G_l^{v})$$|\n",
    "|$$B_l^v$$|$$M^{XY}$$|$$T \\Big(1+\\sum_{k=1}^{l}\\sum_{S:v \\in S}s(R_k^S) + \\sum_{k=1}^{l}s(G_k^v)\\Big) 2 \\beta_l$$|$$s(B_l^{v})$$|\n",
    "\n",
    "<div style=\"text-align:center\">Table 1: Detailed measurement information of MB-QAOA </div>\n",
    "\n",
    "where $1 \\leq v \\leq n$ is the index of linear item with coefficient $\\eta_v$ after variable substitution, $S$ is the index set of non-linear item with coefficient $\\eta_S$, $\\beta_l, \\gamma_l$ ($1 \\leq l \\leq p$) are the training parameters, $M^{XY}$ denotes measurements in the $XY$ plane, $M^{YZ}$ denotes measurements in the $YZ$ plane, the summation $\\sum_{k=1}^0$ is set to be $0$, $T(x)$ is a function $T(x) = (-1)^x$. Each $R_k^S$ denotes a red vertex in Figure 2, whose measurement outcome is $s(R_k^S)$. Each $G_k^v$ denotes a green vertex in Figure 2, whose measurement outcome is $s(G_k^v)$. Each $B^v$ denotes a blue vertex in Figure 2, whose measurement outcome is $s(B_k^v)$.\n",
    "\n",
    "For users' convenience, we provide a function `adaptive_angle` in `qaoa` to calculate measurement angles for MB-QAOA from Table 1, which takes arguments from the outcome dictionary, qubit's label, training parameters and polynomial's coefficients.\n",
    "\n",
    "We can directly import this function with the following line:\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import adaptive_angle\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Byproduct correction\n",
    "\n",
    "After the above measurements, the state on the rightmost gray vertices will be $|\\gamma,\\beta\\rangle$, with byproducts applied to it. The byproduct for the logical qubit $v$ is $X^{x}Z^{z}  $ with\n",
    "\n",
    "$$\n",
    "x = \\sum_{k=1}^{p} s(B_{k}^{v}), \\quad z = \\sum_{k=1}^{p} \\sum_{S: v\\in S} s(R_k^S) + \\sum_{k=1}^{p} s(G_k^v).\\tag{12}\n",
    "$$\n",
    "\n",
    "To obtain the expected quantum state $|\\gamma,\\beta\\rangle$, we need to correct these byproducts after measurements. For users' convenience, we provide a function `byproduct_power` in `qaoa` to calculate the power of byproducts, which takes arguments from the type of byproducts, vertex, MB-QAOA graph, outcome dictionary, and circuit depth. \n",
    "\n",
    "We can directly import this function with the following line:\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import byproduct_power\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code Implementation\n",
    "\n",
    "Next, we will use our MBQC module to simulate MB-QAOA. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### State evolution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import the required modules\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "from paddle_quantum.mbqc.utils import pauli_gate, kron, basis, permute_systems\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import preprocess, adaptive_angle, byproduct_power"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define MB-QAOA\n",
    "def mbqc_qaoa(poly_x, depth, gamma, beta):\n",
    "    \n",
    "    # Preprocess the objective function and obtain the MB-QAOA graph\n",
    "    poly_classified, QAOA_graph = preprocess(poly_x, depth)\n",
    "    var_num, cons_item, linear_items, non_linear_items = poly_classified\n",
    "\n",
    "    # Instantiate a MBQC class and set the graph\n",
    "    mbqc = MBQC()\n",
    "    mbqc.set_graph(graph=QAOA_graph)\n",
    "\n",
    "    # Measure every qubit\n",
    "    for i in range(1, depth + 1):\n",
    "        \n",
    "        # Measure red vertices\n",
    "        for item in non_linear_items:\n",
    "            angle_r = adaptive_angle(which_qubit=('R', item[0], i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=gamma[i - 1],\n",
    "                                     eta=to_tensor(item[1], dtype='float64')\n",
    "                                     )\n",
    "            mbqc.measure(which_qubit=('R', item[0], i), basis=basis('YZ', angle_r))\n",
    "\n",
    "        # Measure green vertices\n",
    "        for v in range(1, var_num + 1):\n",
    "            angle_g = adaptive_angle(which_qubit=('G', v, i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=gamma[i - 1],\n",
    "                                     eta=linear_items[v])\n",
    "            mbqc.measure(which_qubit=('G', v, i), basis=basis('XY', angle_g))\n",
    "\n",
    "        # Measure blue vertices\n",
    "        for v in range(1, var_num + 1):\n",
    "            angle_b = adaptive_angle(which_qubit=('B', v, i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=beta[i - 1],\n",
    "                                     eta=to_tensor([1], dtype='float64'))\n",
    "            mbqc.measure(which_qubit=('B', v, i), basis=basis('XY', angle_b))\n",
    "\n",
    "    # Correct byproduct operators\n",
    "    for v in range(1, var_num + 1):\n",
    "        pow_x = byproduct_power(gate='X', v=v, graph=mbqc.get_graph(), outcome=mbqc.get_classical_output(), depth=depth)\n",
    "        pow_z = byproduct_power(gate='Z', v=v, graph=mbqc.get_graph(), outcome=mbqc.get_classical_output(), depth=depth)\n",
    "        mbqc.correct_byproduct(gate='X', which_qubit=('H', v, depth), power=pow_x)\n",
    "        mbqc.correct_byproduct(gate='Z', which_qubit=('H', v, depth), power=pow_z)\n",
    "        \n",
    "    output_label = [('H', i, depth) for i in range(1, var_num + 1)]\n",
    "\n",
    "    # Permute the system order to fit output_label\n",
    "    state_out = permute_systems(mbqc.get_quantum_output(), output_label)\n",
    "    \n",
    "    return state_out.vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MB-QAOA optimization neural network\n",
    "\n",
    "The procedure of building an optimization neural network is similar to most quantum machine learning tutorials on Paddle Quantum, with the only difference of setting the forward propagation by `mbqc_qaoa`. We will obtain the evolved state and calculate the expectation value of Hamiltonian $H_{C}$ in that state as the loss function. Then, we use Paddle optimizer to minimize loss with gradient descent algorithm and update the training parameters $\\gamma_1, ... \\gamma_p, \\beta_1, ... \\beta_p$ to the optimal ones.\n",
    "\n",
    "We provide a function `expecval` in `qaoa` to calculate the expectation value $\\langle \\gamma,\\beta| H_C| \\gamma,\\beta\\rangle$ of a Hamiltonian $H_C$ in the state $|\\gamma,\\beta\\rangle$ 。\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import expecval\n",
    "```\n",
    "\n",
    "The code implementation of the MB-QAOA optimization net is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import Paddle optimizer\n",
    "from paddle import nn\n",
    "# Import the expecval function\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import expecval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the optimization net with MB-QAOA\n",
    "class MBQC_QAOA_Net(nn.Layer):\n",
    "\n",
    "    def __init__(self, depth, dtype=\"float64\"):\n",
    "        \n",
    "        super(MBQC_QAOA_Net, self).__init__()\n",
    "        \n",
    "        self.depth = depth\n",
    "        \n",
    "        # Define the training parameters\n",
    "        self.gamma = self.create_parameter(shape=[self.depth],\n",
    "                                           default_initializer=nn.initializer.Uniform(low=0.0, high=2 * pi),\n",
    "                                           dtype=dtype,\n",
    "                                           is_bias=False)\n",
    "        self.beta = self.create_parameter(shape=[self.depth],\n",
    "                                          default_initializer=nn.initializer.Uniform(low=0.0, high=2 * pi),\n",
    "                                          dtype=dtype,\n",
    "                                          is_bias=False)\n",
    "        \n",
    "    # Define the forward propagation with input polynomial\n",
    "    def forward(self, poly):\n",
    "        \n",
    "        # Run the MB-QAOA algorithm and return the ouput state vector\n",
    "        vector_out = mbqc_qaoa(poly, self.depth, self.gamma, self.beta)\n",
    "        \n",
    "        # Get the cost Hamiltonian\n",
    "        HC = get_cost_hamiltonian(poly)\n",
    "        \n",
    "        # Calculate expectation value and set it as a loss function\n",
    "        loss = - expecval(vector_out, HC)\n",
    "        \n",
    "        # Return loss and state\n",
    "        return loss, vector_out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decoding the solution\n",
    "\n",
    "After implementing the optimization neural network, we can obtain the optimal parameters $\\gamma^*,\\beta^*$, and the corresponding output state $|\\gamma^*,\\beta^*\\rangle$. It remains to extract the bit string as the final optimal solution to the original PUBO problem. For this, we need to measure the state $|\\gamma^*,\\beta^*\\rangle$ of a sufficient number of times to estimate the probability distribution of all binary strings and take the most probable one as our final solution. For this, we provide a function `get_solution_string` in `qaoa` to decode the quantum output.\n",
    "\n",
    "We can directly import this function with the following line:\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import get_solution_string\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Examples\n",
    "\n",
    "After introducing the above MB-QAOA algorithm, we will apply it to two specific examples which are then simulated by our MBQC module. In the examples, we will directly call `MBQC_QAOA_Net` in `qaoa` to instantiate an MB-QAOA optimization network. Please refer to the following tutorial for more details:\n",
    "\n",
    "- [Polynomial Unconstrained Boolean Optimization Problem in MBQC](PUBO_EN.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Farhi, Edward, et al. \"A quantum approximate optimization algorithm.\" [arXiv preprint arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)\n",
    "\n",
    "[2] Farhi, Edward, et al. \"Quantum computation by adiabatic evolution.\" [arXiv preprint quant-ph/0001106 (2000).](https://arxiv.org/abs/quant-ph/0001106)\n",
    "\n",
    "[3] Duan, Runyao. \"Quantum adiabatic theorem revisited.\" [arXiv preprint arXiv:2003.03063 (2020).](https://arxiv.org/abs/2003.03063)\n",
    "\n",
    "[4] Ferguson, R. R., et al. \"Measurement-based variational quantum eigensolver.\" [Physical Review Letters 126.22 (2021): 220501-220501.](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.126.220501)\n",
    "\n",
    "[5] Browne, Dan, and Hans Briegel. \"One-way quantum computation.\" [Quantum Information: From Foundations to Quantum Technology Applications (2016): 449-473.](https://onlinelibrary.wiley.com/doi/abs/10.1002/9783527805785.ch21)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "73e152e9b81fe728e387c249fa9090f02d423820fe8ab6018c11ce80df71d553"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
